package kth.csc.inda;

public class GraphTester {
	public static void main(String[] args) {
        new GraphTester(1000);
    }
	
	private final int size;
	private final boolean DEBUG=false;
	Stopwatch clock = new Stopwatch();
	
	public GraphTester(int n){
		size = n;
		ListGraph lg = new ListGraph(size);
		MatrixGraph mg = new MatrixGraph(size);
		for(int i=0;i<size*2;i++){
			int random1 = (int) (Math.random()*size);
			int random2 = (int) (Math.random()*size);
			lg.addEdge(random1, random2);
			mg.addEdge(random1, random2);
		}
		
		long temptime=0;
		clock.reset().start();
		depthSearch(lg);
		temptime = clock.stop().getTime();
		System.out.println("The time it took to do the search for the ListGraph was "+temptime+" ms");
		
		clock.reset().start();
		depthSearch(mg);
		temptime = clock.stop().getTime();
		System.out.println("The time it took to do the search for the MatrixGraph was "+temptime+" ms");
	}
	private void depthSearch(UndirectedGraph g){
		boolean[] visited = new boolean[g.numVertices()];
		int counter = 0;
		int components=0;
		int largest=0;
		for(boolean b:visited){
			if(!b){
				components++;
				int x 	= depthFirstSearch(g, counter, visited);
				largest	= x>largest? x : largest;
				if(DEBUG){System.out.println(x);}
			}
			counter++;
		}
		System.out.println("This graph has "+components+" components and the largets one is "+largest+" nodes");
	}
	private int depthFirstSearch(UndirectedGraph g, int a, boolean[] visited) {
		int x = 1;
        if (DEBUG) {
            System.out.println("[=> DFS a=" + a + " " + visited[a] + "]");
        }
        if (visited[a]) {
            return 0;
        }
        
        visited[a] = true;

        final VertexIterator vi = g.adjacentVertices(a);
        while (vi.hasNext()) {
            x = x + depthFirstSearch(g, vi.next(), visited);
        }
        if (DEBUG) {
            System.out.println("[<= DFS a=" + a + "]");
        }
        return x;
    }
}
